/*
 * cm_buddy.c
 *
 *  Created on: Sep 18, 2015
 *      Author: song
 */

#include "cm_buddy_alg.h"
#include <cm/cm_math.h>

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

// 用数组表示的完全二叉树，其父子节点序号的对应关系
#define LEFT_LEAF(index)  ((index + 1) * 2 - 1)
#define RIGHT_LEAF(index)  ((index +1 ) * 2)
#define PARENT(index)   ((index + 1) / 2 - 1)

struct buddy2 {
    unsigned size;  // 节点的大小, 若已分配则置为0
    unsigned longest[1]; // 并不分配空间，只是用来方便访问各个节点
};

static inline int fixsize(int size)
{
    return (min_power_of_2_eg(size));
}

/*
 * @brief   构造一个管理 size 个内存单元的 伙伴管理位图
 */
struct buddy2* buddy2_new(int size)
{
    struct buddy2* self;
    unsigned node_size;
    int i;

    if (size < 1 || !is_power_of_2(size)) // 内存单元个数必须是2的幂次
        return NULL;

    self = (struct buddy2*) ALLOC(2 * size * sizeof(unsigned));
    if (self == NULL)
        return NULL;

    self->size = size;
    node_size = size * 2; // 在下面循环开始时，因为0是2的幂次，node_size即除以2

    for (i = 0; i < 2 * size - 1; ++i) {
        if (is_power_of_2(i + 1))
            node_size /= 2;
        self->longest[i] = node_size;
    }

    return self;
}

int buddy2_alloc(struct buddy2* self, int size)
{
    unsigned index = 0;
    unsigned node_size;
    unsigned offset = 0;

    if (self == NULL || size <= 0)
        return -1;

    if (!is_power_of_2(size)) // 一次分配的单元数也是2的幂次
        size = fixsize(size);

    if (self->longest[index] < size) // 没有空间了
        return -1;

    // 循环将index定位到有足够空间的序号处
    for (node_size = self->size; node_size > size; node_size /= 2) {
        printf("nodesize=%d, size=%d, left=%d, right=%d", node_size, size,
                self->longest[LEFT_LEAF(index)],
                self->longest[RIGHT_LEAF(index)]);
        if (self->longest[LEFT_LEAF(index)] >= size) {
            index = LEFT_LEAF(index);
            printf("  use left\n");
        } else if (self->longest[RIGHT_LEAF(index)] >= size) {
            index = RIGHT_LEAF(index);
            printf("  use right\n");
        } else {
            printf("Can't alloc because outer slice 1.\n");
            return -1;
        }
    }

    if (node_size < size) {
        printf("Can't alloc because outer slice 2.\n");
        return -1;
    }

    assert(self->longest[index] == size);
    // 分配出去的节点置为0
    self->longest[index] = 0;

    // 节点序号 idx, 节点在本层偏移 off, 树总层数n, 节点idx在第m层, 第m层第一个节点序号idxm, 序号和层数全部从1开始
    // off = idx - idxm
    // idxm = 2 ^ (m - 1)
    //
    offset = (index + 1) * node_size - self->size;

    while (index) {
        index = PARENT(index);
        self->longest[index] = (self->longest[LEFT_LEAF(index)]
                + self->longest[RIGHT_LEAF(index)]);
    }

    return offset;
}

void buddy2_free(struct buddy2* self, int offset)
{
    unsigned node_size, index = 0;
    unsigned left_longest, right_longest;

    // assert(self && offset >= 0 && offset < self->size);
    if (!(self && offset >= 0 && offset < self->size))
        return;

    node_size = 1;

    // 根据分配的块offset计算该块在完全二叉树中的序号，是个叶子节点，叶子节点块的node_size都是1
    index = offset + self->size - 1;

    // index是叶子节点，而不一定是分配出去的那个节点，分配出去的节点已设置为0了
    // 向上遍历父节点，找到被设置为0的点，并计算出这个节点的大小
    for (; self->longest[index]; index = PARENT(index)) {
        node_size *= 2;
        if (index == 0) // 连根节点都被分配了
            return;
    }

    // 被分配的节点设置为原来的大小了，而分配的时候其实并没有改变它子节点的大小
    self->longest[index] = node_size;

    // 因为分配时改变了父节点们的大小，现在要把父节点还原
    while (index) { // 一直遍历到根节点,  index == 0的时候
        index = PARENT(index);
        node_size *= 2;

        left_longest = self->longest[LEFT_LEAF(index)];
        right_longest = self->longest[RIGHT_LEAF(index)];

        if (left_longest + right_longest == node_size)
            self->longest[index] = node_size;
        else
            self->longest[index] = (left_longest + right_longest);
    }
}
